package leetcode_41_60;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class totalNQueens_52 {
    /**
     * 类似N皇后解法
     * @param n
     * @return
     */
    public int totalNQueens(int n) {
        //array[i]表示第i行对应皇后列的下标
        int[] array = new int[n];
        //从第一行开始从头开始遍历
        dfs(0,array,n);
        return res;
    }
    int res=0;
    public void dfs(int row,int[] array,int n){
        //每一行都有对应的皇后，此时满足条件，将Q添加进数组中，添加结果返回
        if(row == n){
            res+=1;
            return ;
        }
        //从每一行开始遍历，这样能保证行是绝对不会发生冲突的，因为他是递增的
        for(int i = 0;i<n;i++){
            //将第x行设置为第i列
            array[row] = i;
            //判断位置是否冲突，flag变量控制循环跳出
            boolean flag = true;
            //j<row，即判断当前行的Q与之前的Q是否冲突
            for(int j = 0;j<row;j++){
                //array[j] == array[row]判断   同一列
                //Math.abs(row-j) == Math.abs(array[row]-array[j])  判断  正负对角线上
                if(array[j] == array[row] || Math.abs(row-j) == Math.abs(array[row]-array[j])){
                    //发生冲突，则直接跳出循环
                    flag = false;
                    break;
                }
            }
            //当前列存在冲突，寻找下一列
            if(!flag)continue;
            //不冲突，则放下一个皇后 x+1
            dfs(row+1,array,n);
        }
    }


    /**
     * 0ms
     * 评论区思路
     * 位运算
     *   & 按位与  同真才为真，即都为1该位结果才为1
     *   x & -x   表示只保存x 最右边的1，其余1都变为0
     *   x & x-1 表示把x最右边的1变为0
     *
     *   |   按位或  同假才为假
     *   ~ 位取反操作
     * @param n
     * @return
     */
    public int totalNQueens2(int n) {
        if(n<=0 || n>32){
            return 0;
        }
        int limit = n==32?-1:(1<<n)-1;
        return proces(limit,0,0,0);
    }

    /**
     * @param limit  n位全部为1的二进制数字
     * @param col     已经有Q的列
     * @param left    因为Q的左斜线影响的列
     * @param right 因为Q的右斜线影响的列
     * @return
     */
    private int proces(int limit, int col, int left, int right) {
        if(limit == col){
            return 1;
        }
        int pos = limit & (~(col|left|right));//表示当前这一行中可以放n皇后的位置
        // 例 1111 & ( ~( 0010   |  0100   |  0001 ))  = 1000
        int res = 0;
        int mostRight = 0;   //二进制最右边的1
        while(pos!=0){  //只要数字不为0，说明还存在1，即还有可以放n皇后的位置，
            //x & -x   表示只保存x 最右边的1，其余1都变为0
            mostRight = pos&(-pos);  //表示从最右边开始填，直到全部完成           例  1000
            pos = pos-mostRight;              //每次填个最右边的就让pos的最右边为0，直到pos整个为0    例  1000-1000 =0000
            //进入下一行 ，将下一列对应列和左右对角线位置变为1         1111   1010（col）    0000（1左移一位）   0100 （1右移一位）
            res+=proces(limit,(col|mostRight),(left|mostRight)<<1,(right|mostRight)>>>1);
        }
        return res;
    }

}
